package com.sx.sx1.lintcode.day717;

public class LC201 {


     static class SegmentTreeNode {
          public int start, end;
          public SegmentTreeNode left, right;
          public SegmentTreeNode(int start, int end) {
              this.start = start;
              this.end = end;
              this.left = this.right = null;
          }
      }



    static class Solution {
        /*
         * @param start: start value.
         * @param end: end value.
         * @return: The root of Segment Tree.
         */
        public SegmentTreeNode build(int start, int end) {
            if(start> end) return null;
            if(start == end) return  new SegmentTreeNode(start,end);
            SegmentTreeNode root = new SegmentTreeNode(start,end);
            int m  = start+(end-start)/2;
            root.left = build(start,m);
            root.right = build(m+1,end);
            return  root;
        }
    }


}

/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
avatar
您有887条未读消息，请及时查看
新增3条赞
201 · 线段树的构造
算法
中等
通过率
44%

题目
题解7
笔记
讨论99+
排名
记录
描述
线段树是一棵二叉树，他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:

根节点的 start 和 end 由 build 方法所给出。
对于节点 A 的左儿子，有 start=A.start, end=(A.start + A.end) / 2。
对于节点 A 的右儿子，有 start=(A.start + A.end) / 2 + 1, end=A.end。
如果 start 等于 end, 那么该节点是叶子节点，不再有左右儿子。
实现一个 build 方法，接受 start 和 end 作为参数, 然后构造一个代表区间 [start, end] 的线段树，返回这棵线段树的根。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


线段树(又称区间树), 是一种高级数据结构，他可以支持这样的一些操作:

查找给定的点包含在了哪些区间内
查找给定的区间包含了哪些点
见百科：
线段树
区间树

样例
样例 1:

输入：[1,4]
输出："[1,4][1,2][3,4][1,1][2,2][3,3][4,4]"
解释：
	               [1,  4]
	             /        \
	      [1,  2]           [3, 4]
	      /     \           /     \
	   [1, 1]  [2, 2]     [3, 3]  [4, 4]
样例 2:

输入：[1,6]
输出："[1,6][1,3][4,6][1,2][3,3][4,5][6,6][1,1][2,2][4,4][5,5]"
解释：
	       [1,  6]
             /        \
      [1,  3]           [4,  6]
      /     \           /     \
   [1, 2]  [3,3]     [4, 5]   [6,6]
   /    \           /     \
[1,1]   [2,2]     [4,4]   [5,5]
相关知识
学习《 高级数据结构：线段树、树状数组》课程中的1.7如何构建线段树相关内容 ，了解更多相关知识！
标签
相关题目

439
线段树的构造 II
中等

203
线段树的修改
中等

202
线段树的查询
中等

751
约翰的生意
中等

247
线段树查询 II
中等

201
线段树的构造
中等
推荐课程

系统设计 System Design 2024版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
已开启智能提示
发起考试
30 分 00 秒
1234567891011121314151617181920212223
/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 *     public int start, end;
 *     public SegmentTreeNode left, right;
 *     public SegmentTreeNode(int start, int end) {
 *         this.start = start, this.end = end;
 *         this.left = this.right = null;
 *     }
 * }

控制台
历史提交

 */
